\documentclass[supercite]{Experimental_Report}

\title{~~~~~~编译原理实验~~~~~~}
\author{崔昊阳}
\school{计算机科学与技术学院}
\classnum{CS2104}
\stunum{U202115415}
\instructor{赵小松} % 该系列实验报告模板有华科大计院教师陈加忠制作
\date{2024年6月5日}

\usepackage{algorithm, multirow}
\usepackage{algpseudocode}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{mathtools}
\usepackage{subcaption}
\usepackage{xltxtra} %提供了针对XeTeX的改进并且加入了XeTeX的LOGO, 自动调用xunicode宏包(提供Unicode字符宏)
\usepackage{bm}
\usepackage{tikz}
\usepackage{tikzscale}
\usepackage{pgfplots}
\usepackage{xcolor}
\usepackage{listings}
\lstset{
    language = C,
    backgroundcolor = \color{gray!20},    % 背景色
    basicstyle = \small\ttfamily,           % 基本样式 + 小号字体
    rulesepcolor= \color{white},             % 代码块边框颜色
    breaklines = true,                  % 代码过长则换行
    numbers = left,                     % 行号在左侧显示
    numberstyle = \small,               % 行号字体
    keywordstyle = \color{black}\bfseries,      % 关键字颜色
	identifierstyle=\color{black}, 		% 标识符颜色
    commentstyle =\color{black},        % 注释颜色
    stringstyle = \color{black},          % 字符串颜色
    % frame = shadowbox,                  % 用（带影子效果）方框框住代码块
    showspaces = false,                 % 不显示空格
    columns = flexible,                    % 字间距固定
}

\pgfplotsset{compat=1.16}

\newcommand{\cfig}[3]{
  \begin{figure}[htb]
    \centering
    \includegraphics[width=#2\textwidth]{images/#1.tikz}
    \caption{#3}
    \label{fig:#1}
  \end{figure}
}

\newcommand{\sfig}[3]{
  \begin{subfigure}[b]{#2\textwidth}
    \includegraphics[width=\textwidth]{images/#1.tikz}
    \caption{#3}
    \label{fig:#1}
  \end{subfigure}
}

\newcommand{\xfig}[3]{
  \begin{figure}[htb]
    \centering
    #3
    \caption{#2}
    \label{fig:#1}
  \end{figure}
}

\newcommand{\rfig}[1]{\autoref{fig:#1}}
\newcommand{\ralg}[1]{\autoref{alg:#1}}
\newcommand{\rthm}[1]{\autoref{thm:#1}}
\newcommand{\rlem}[1]{\autoref{lem:#1}}
\newcommand{\reqn}[1]{\autoref{eqn:#1}}
\newcommand{\rtbl}[1]{\autoref{tbl:#1}}

\algnewcommand\Null{\textsc{null }}
\algnewcommand\algorithmicinput{\textbf{Input:}}
\algnewcommand\Input{\item[\algorithmicinput]}
\algnewcommand\algorithmicoutput{\textbf{Output:}}
\algnewcommand\Output{\item[\algorithmicoutput]}
\algnewcommand\algorithmicbreak{\textbf{break}}
\algnewcommand\Break{\algorithmicbreak}
\algnewcommand\algorithmiccontinue{\textbf{continue}}
\algnewcommand\Continue{\algorithmiccontinue}
\algnewcommand{\LeftCom}[1]{\State $\triangleright$ #1}

\newtheorem{thm}{定理}[section]
\newtheorem{lem}{引理}[section]

\colorlet{shadecolor}{black!15}

\theoremstyle{definition}
\newtheorem{alg}{算法}[section]

\def\thmautorefname~#1\null{定理~#1~\null}
\def\lemautorefname~#1\null{引理~#1~\null}
\def\algautorefname~#1\null{算法~#1~\null}

\begin{document}

\maketitle

\clearpage

\pagenumbering{Roman}

\tableofcontents[level=2]

\clearpage

\pagenumbering{arabic}

\section{编译工具链的使用}
\subsection{实验任务}
\begin{enumerate}
	\item 编译工具链的使用；
	\item Sysy 语言及运行时库；
	\item 目标平台 arm 的汇编语言；
	\item 目标平台 riscv64 的汇编语言；
\end{enumerate}

以上任务中(1)(2)为必做任务，(3)(4)中任选一个完成即可。

\subsubsection{编译工具链的使用}
本任务包含 4 个子任务，各子任务的具体要求如下：
\begin{enumerate}
	\item GCC 编译器的使用：用 gcc 编译器编译 \texttt{def-test.c} 和 \texttt{alibaba.c} , 并指定合适的编译选项，生成二进制可执行代码 \texttt{def-test}。执行的结果应当包括 Bilibili 的自我介绍以及 Alibaba 对 BiliBili 的喊话。
	\item CLANG 编译器的使用：用 clang 编译器把程序 \texttt{bar.c} “翻译”成优化的(优化级别 O2)armv7 架构，linux 系统，符合 gnueabihf 嵌入式二进制接口规则，并支持 arm 硬浮点的汇编代码。
	\item 交叉编译器 arm-linux-gnueabihf-gcc 和 qemu-arm 虚拟机的使用：用交叉编译器 arm-linux-gnueabihf-gcc 将源程序“翻译”成 arm 汇编代码，再将汇编代码汇编并与 Sysy2022 运行时库连接，生成 arm 可执行代码，然后用 qemu-arm 虚拟机运行 arm 可执行程序。
	\item make 的使用：编写一个 Makefile，使用 make 完成 helloworld 项目的构建。
\end{enumerate}
\subsubsection{Sysy 语言及运行时库}
本任务要求使用 Sysy 语言编写一个程序实现下述功能：
给定一个数组 \texttt{prices} ，它的第 \texttt{i} 个元素 \texttt{prices[i]} 表示一支给定股票第 \texttt{i} 个交易日的价格(假定股价是整数)。你只能选择某个交易日买入这只股票，并选择在未来的另一个交易日卖出该股票。设计一个算法来计算你所能获取的最大利润，并返回这个最大利润值。如果你不能获取任何利润，返回 0 。
\subsubsection{目标平台 riscv64 的汇编语言}
本任务要求用 RISCV 汇编编写一个按升序对数组进行排序的 riscv64 汇编函数。

\subsection{实验实现}
\subsubsection{编译工具链的使用}
对于子任务 1，通过观察 \texttt{alibaba.c} 和 \texttt{def-test.c}，我们发现需要在编译阶段定义宏 \texttt{BILIBILI}，而宏定义可以使用 \texttt{-D} 参数。所以，编译命令可以编写如下。
\begin{lstlisting}
  gcc def-test.c alibaba.c -o def-test -D BILIBILI
\end{lstlisting}
% \begin{figure}[H]
% 	\begin{center}
% 		\includegraphics[scale=0.30]{images/1-1-1.png}
% 		\caption{实验 1 任务 1-1 解答}
% 		\label{1-1-1}
% 	\end{center}
% \end{figure}

对于子任务 2，根据要求，我们可以将 \texttt{target} 设置成 \texttt{armv7-linux-gnueabihf}，同时还要设置优化选项 \texttt{-O2} 和 编译选项 \texttt{-S}。
最终的编译命令如下。
\begin{lstlisting}
  clang bar.c -o bar.clang.arm.s -S -O2 -target armv7-linux-gnueabihf
\end{lstlisting}
% \begin{figure}[H]
% 	\begin{center}
% 		\includegraphics[scale=0.25]{images/1-1-2.png}
% 		\caption{实验 1 任务 1-2 解答}
% 		\label{1-1-2}
% 	\end{center}
% \end{figure}

对于子任务 3，根据要求，我们首先使用 arm-linux-gnueabihf-gcc 将 \texttt{iplusf.c}编译成 arm 汇编代码 \texttt{iplusf.arm.s}。
我们将编译选项设置成 \texttt{-S} 使得编译器输出汇编代码。
接着，我们使用 arm-linux-gnueabihf-gcc 汇编 \texttt{iplusf.arm.s}，同时连接 SysY2022 的运行时库 sylib.a 生成可执行文件。
最后，我们使用 arm 模拟器 qemu-arm 运行编译出来的可执行程序。最终，编译命令如下。
\begin{lstlisting}
  arm-linux-gnueabihf-gcc iplusf.c -o iplusf.arm.s -S
  arm-linux-gnueabihf-gcc iplusf.arm.s sylib.a -o iplusf.arm
  qemu-arm -L /usr/arm-linux-gnueabihf/ iplusf.arm
\end{lstlisting}
% \begin{figure}[H]
% 	\begin{center}
% 		\includegraphics[scale=0.25]{images/1-1-3.png}
% 		\caption{实验 1 任务 1-3 解答}
% 		\label{1-1-3}
% 	\end{center}
% \end{figure}

对于子任务 4，根据要求，我们编写 helloworld 项目的 Makefile 文件。首先，我们将 SOURCES 设置成 \texttt{main.cc} 和 \texttt{helloworld.cc} 并根据 SOURCES 设置 OBJECTS（将 *.cc 替换成 *.o 即可）。
接着，我们用 EXECUTABLE 指定最终生成的可执行文件的名称。最后，我们在 all 中指定依赖并在 helloworld 中编写 g++ 编译命令。最终的 Makefile 文件的内容如下。
\begin{lstlisting}
  SOURCES = main.cc helloworld.cc
  OBJECTS = $(SOURCES:.cc=.o)
  EXECUTABLE = helloworld

  all: $(SOURCES) $(EXECUTABLE)

  helloworld: $(OBJECTS)
    g++ $(OBJECTS) -o $@
    
  .cc.o:
    g++ -c -Iinclude $< -o $@
\end{lstlisting}
% \begin{figure}[H]
% 	\begin{center}
% 		\includegraphics[scale=0.25]{images/1-1-4.png}
% 		\caption{实验 1 任务 1-4 解答}
% 		\label{1-1-4}
% 	\end{center}
% \end{figure}

\subsubsection{Sysy 语言及运行时库}
为了仅遍历数组一次就可以得到答案，我们定义一个 min 变量来动态维护数组的前缀最小值。
在遍历数组的过程中，我们首先使用当前访问到的值更新前缀最小值，在求当前值和前缀最小值之差，取这个差的最大值作为答案。
Sysy 代码如下。
\begin{lstlisting}
  int maxProfit(int prices[]){
    const int INF = 10000;
    int ret = 0, min = INF;
    int i = 0;
    while (i < N)
    {
        int p = prices[i];
        if (min > p)
        {
            min = p;
        }
        if (ret < p - min)
        {
            ret = p - min;
        }
        i = 1 + i;
    }
    return ret;
}
\end{lstlisting}
% \begin{figure}[H]
% 	\begin{center}
% 		\includegraphics[scale=0.25]{images/1-2.png}
% 		\caption{实验 1 任务 2 解答}
% 		\label{1-2}
% 	\end{center}
% \end{figure}

\subsubsection{目标平台 riscv64 的汇编语言}
子任务 3 和 4 二选一即可，我们选择子任务 4。本任务需要编写 bubblesort 的 RISC-V 汇编代码。逐句注释的汇编代码如下。
\begin{lstlisting}
  .text                       # 指示下面是代码段
  .align  1                   # 对齐到1字节边界
  .globl  bubblesort          # 声明 bubblesort 是一个全局函数
  .type   bubblesort, @function # 声明 bubblesort 的类型是函数
bubblesort:
addiw	a5,a1,-1            # a5 = a1 - 1 (a1 保存数组长度)
ble	a5,zero,.L2          # 如果 a5 <= 0，跳转到.L2（数组长度 <= 1，直接返回）
addi	a6,a0,4             # a6 = a0 + 4 (a0 保存数组首地址)

.L3:
addiw	a1,a5,-1            # a1 = a5 - 1
slli	a2,a1,32            # a2 = a1 << 32 （逻辑左移 32 位）
srli	a2,a2,30            # a2 = a2 >> 30 （逻辑右移 30 位，结果是 a1 * 4）
mv	a5,a0                # a5 = a0 （数组首地址）
add	a2,a2,a6            # a2 = a2 + a6 （a2 现在是数组的终止地址）

.L5:
lw	a3,0(a5)             # 加载数组中的第一个元素到 a3 中
lw	a4,4(a5)             # 加载数组中的第二个元素到 a4 中
ble	a3,a4,.L4            # 如果 a3 <= a4，跳转到.L4
sw	a3,4(a5)             # 否则交换 a3 和 a4
sw	a4,0(a5)

.L4:
addi	a5,a5,4             # a5 = a5 + 4 (移动到下一个元素位置)
bne	a2,a5,.L5            # 如果 a5 != a2，跳转到.L5 (继续比较下一个元素)
sext.w	a5,a1               # 将 a1 符号扩展到 a5
bne	a5,zero,.L3          # 如果 a5 != 0，跳转到.L3 (开始下一轮排序)

.L2:
  li      a0,0               # a0 = 0 （返回值设为 0）
  ret                        # 返回
  .size   bubblesort, .-bubblesort # bubblesort 函数的大小

\end{lstlisting}

\newpage
\section{词法分析}
\subsection{实验任务}
本实验要求利用 flex 工具生成 SysY2022 语言的词法分析器，要求输入一个 SysY2022 语言源程序文件,比如 \texttt{test.c}，词法分析器能输出该程序的 token 以及 token 的种别。
具体而言，本实验需要在文件 \texttt{sysy.l} 中补充适当的代码，设计识别 SysY2022 语言单词符号的词法分析器。
需要补充的内容有：
\begin{enumerate}
  \item 标识符 ID;
  \item int 型字面量 INT\_LIT;
  \item float 型字面量 FLOAT\_LIT;
  \item 词法错误
\end{enumerate}

\subsection{词法分析器的设计与实现}
首先我们需要写出识别标识符、int 型字面量、float 型字面量以及错误标识符、错误八进制数、错误浮点数等各种词法错误的正则表达式。
其中，标识符的第一个字符必须是字母或下划线，后续字符可以是字母、数字或下划线。
这可以通过正则表达式 IDENTIFIER 来实现，匹配以字母或下划线开头，后跟零个或多个字母、数字或下划线的字符串；
int 型字面量包括十进制、十六进制和八进制数，可以通过正则表达式 INTEGER 来匹配，
其中\texttt{[+-]?}表示可选的正负号，\texttt{[1-9][0-9]*}表示匹配非零开头的十进制数，\texttt{0[xX]([0-9A-Fa-f])+}表示匹配以 0x 或 0X 开头的十六进制数，\texttt{0[0-7]*} 表示匹配八进制数；
float 型字面量可以通过正则表达式 FLOAT 来匹配，其中考虑了不同形式的浮点数表示法。
FLOAT 中的三个子表达式分别匹配整数部分无数字，小数部分是数字或使用科学计数法和可选的 f 或 F 的情况；整数部分有数字，小数部分是数字或使用科学计数法和可选的 f 或 F 的情况以及直接使用科学计数法的情况。
为了识别错误的八进制数，我们使用正则表达式 ERR\_OCT，匹配以 0 开头后跟一个或多个非八进制数字的字符串；
错误的标识符可以通过正则表达式 ERR\_IDENTITIFER 来匹配，表示以数字开头后跟一个或多个字母、数字或下划线的字符串；
错误的浮点数可以通过正则表达式 ERR\_FLOAT 来匹配，表示以数字开头紧跟 f 或 F 的字符串。
所有新加入的正则表达式如下。
\begin{lstlisting}
  IDENTIFIER [A-Za-z_][A-Za-z0-9_]*
  INTEGER [+-]?[1-9]{DIGIT}*|0[xX]({DIGIT}|[0-9A-Fa-f])+|0[0-7]*
  FLOAT [+-]?(([.]{DIGIT}+([eE][+-]?{DIGIT}+)?[fF]?)|({DIGIT}+[.]{DIGIT}*([eE][+-]?{DIGIT}+)?[fF]?)|({DIGIT}+[eE][+-]?{DIGIT}+[fF]?))
  ERR_OCT 0[0-9A-Fa-f]+
  ERR_IDENTITIFER {DIGIT}[A-Za-z0-9_]+
  ERR_FLOAT {DIGIT}[fF]
\end{lstlisting}
% \begin{figure}[H]
% 	\begin{center}
% 		\includegraphics[scale=0.25]{images/2-2-1.png}
% 		\caption{实验 2 的正则表达式}
% 		\label{2-2-1}
% 	\end{center}
% \end{figure}

接着，我们要定义词法分析器在匹配到相应 token 之后要做的动作。对于标识符、int 型字面量、float 型字面量，我们打印出值和类别即可。
对于词法错误，我们需要打印出出错 token 的内容和位置。其代码如下。
\begin{lstlisting}
  {FLOAT} {printf("%s : FLOAT_LIT\n", yytext); return FLOAT_LIT; }
  {IDENTIFIER} {printf("%s : ID\n", yytext); return ID; }
  {INTEGER} {printf("%s : INT_LIT\n", yytext); return INT_LIT; }
  {ERR_OCT} { printf("Lexical error - line %d : %s\n", yylineno, yytext); }
  {ERR_IDENTITIFER} { printf("Lexical error - line %d : %s\n", yylineno, yytext); }
  {ERR_FLOAT} { printf("Lexical error - line %d : %s\n", yylineno, yytext); }
\end{lstlisting}
% \begin{figure}[H]
% 	\begin{center}
% 		\includegraphics[scale=0.25]{images/2-2-2.png}
% 		\caption{实验 2 的代码}
% 		\label{2-2-2}
% 	\end{center}
% \end{figure}

至此，我们完成了此任务。

\newpage
\section{语法分析}
\subsection{实验任务}
本实验要求利用 flex+bison 生成 SysY2022 的语法分析程序。
要求任给一个 SysY202 2语言的源程序，能识别并定位源程序中的语法错误。
完善 \texttt{parser.y} 的语法规则和语义计算规则，实现语法检查和语法分析。
具体要完成的语法规则，是 SysY语言(2022 版)定义中的 stmt 语法部分：。
\begin{lstlisting}
  Stmt → LVal '=' Exp ';' | [Exp] ';' | Block
  | 'if' '( Cond ')' Stmt [ 'else' Stmt ]
  | 'while' '(' Cond ')' Stmt
  | 'break' ';' | 'continue' ';'
  | 'return' [Exp] ';'
\end{lstlisting}
% \begin{figure}[H]
% 	\begin{center}
% 		\includegraphics[scale=0.25]{images/3-2-1.png}
% 		\caption{stmt 语法部分定义}
% 		\label{3-2-1}
% 	\end{center}
% \end{figure}

\subsection{语法分析器的设计与实现}
本任务已经给出了 Stmt 的产生式，所以我们只需要把产生式化成符合 bison 语法要求的代码即可。

Stmt 是一个语句的产生式，其中包含了多种语句类型。对于每种语句类型，我们创建了一个对应的 StmtAST 对象，并设置其类型和相关的成员变量。以下将简要每种语句类型的具体实现。
\begin{enumerate}
  \item 赋值语句 (\texttt{LVal '=' Exp ';'})：创建一个 StmtAST 对象，设置其 sType 为 ASS，并将赋值语句的左值和相应地表达式分别赋值给 lVal 和 exp。
  \item 空语句 (\texttt{';'})：创建一个 StmtAST 对象，设置其 sType 为 SEMI。
  \item 表达式语句 (\texttt{[Exp] ';'})：创建一个 StmtAST 对象，设置其 sType 为 EXP。将表达式赋值给 exp。
  \item 块语句 (\texttt{Block})：创建一个 StmtAST 对象，设置其 sType 为 BLK，并将块赋值给 block。
  \item 条件语句 (\texttt{if '(' Cond ')' Stmt [ 'else' Stmt ]})：这个语句需要用两块代码来表示。创建一个 StmtAST 对象，设置其 sType 为 SEL。创建一个 SelectStmtAST 对象，将判断条件和相应地表达式分别赋值给 cond 和 ifStmt。如果没有 \texttt{ELSE}，则直接结束。否则在另一个块中重复以上操作，并将 else 分支的 Stmt 赋值给 elseStmt。
  \item 循环语句 (\texttt{while '(' Cond ')' Stmt})：创建一个 StmtAST 对象，设置其 sType 为 ITER。创建一个 IterationStmtAST 对象，将循环条件和相应地表达式分别赋值给 cond 和 stmt。
  \item break 语句 (\texttt{'break' ';'})：创建一个 StmtAST 对象，设置其 sType 为 BRE。
  \item continue 语句 (\texttt{'continue' ';'})：创建一个 StmtAST 对象，设置其 sType 为 CONT。
  \item return 语句 (\texttt{'return' [Exp] ';'})：这个语句也需要用两块代码来表示。创建一个 StmtAST 对象，设置其 sType 为 RET。如果是带返回值的 RETURN，则创建一个 ReturnStmtAST 对象，并将表达式赋值给 exp。
\end{enumerate}
至此，我们完成了此任务，完整的代码如下：
% \begin{figure}[H]
% 	\begin{center}
% 		\includegraphics[scale=0.25]{images/3-2-2.png}
% 		\caption{stmt 的 bison 代码}
% 		\label{3-2-2}
% 	\end{center}
% \end{figure}
\begin{lstlisting}
  Stmt:	LVal ASSIGN Exp SEMICOLON {
			$$ = new StmtAST();
			$$->sType = ASS;
			$$->lVal = unique_ptr<LValAST> ($1);
			$$->exp = unique_ptr<AddExpAST> ($3);
		}
		| SEMICOLON {
			$$ = new StmtAST();
			$$->sType = SEMI;
		}
		| Exp SEMICOLON	{
			$$ = new StmtAST();
			$$->sType = EXP;
			$$->exp = unique_ptr<AddExpAST> ($1);
		}
		| Block {
			$$ = new StmtAST();
			$$->sType = BLK;
			$$->block = unique_ptr<BlockAST> ($1);
		}
		| IF LP Cond RP Stmt {
			$$ = new StmtAST();
			$$->sType = SEL;
			$$->selectStmt = unique_ptr<SelectStmtAST> (new SelectStmtAST());
			$$->selectStmt->cond = unique_ptr<LOrExpAST> ($3);
			$$->selectStmt->ifStmt = unique_ptr<StmtAST> ($5);
		}
		| IF LP Cond RP Stmt ELSE Stmt{
			$$ = new StmtAST();
			$$->sType = SEL;
			$$->selectStmt = unique_ptr<SelectStmtAST> (new SelectStmtAST());
			$$->selectStmt->cond = unique_ptr<LOrExpAST> ($3);
			$$->selectStmt->ifStmt = unique_ptr<StmtAST> ($5);
			$$->selectStmt->elseStmt = unique_ptr<StmtAST> ($7);
		}
		| WHILE LP Cond RP Stmt {
			$$ = new StmtAST();
			$$->sType = ITER;
			$$->iterationStmt = unique_ptr<IterationStmtAST> (new IterationStmtAST());
			$$->iterationStmt->cond = unique_ptr<LOrExpAST> ($3);
			$$->iterationStmt->stmt = unique_ptr<StmtAST> ($5);
		}
		| BREAK SEMICOLON {
			$$ = new StmtAST();
			$$->sType = BRE;
		}
		| CONTINUE SEMICOLON {
			$$ = new StmtAST();
			$$->sType = CONT;
		}
		| RETURN SEMICOLON {
			$$ = new StmtAST();
			$$->sType = RET;
			$$->returnStmt = unique_ptr<ReturnStmtAST> (new ReturnStmtAST());
		}
		| RETURN Exp SEMICOLON {
			$$ = new StmtAST();
			$$->sType = RET;
			$$->returnStmt = unique_ptr<ReturnStmtAST> (new ReturnStmtAST());
			$$->returnStmt->exp = unique_ptr<AddExpAST> ($2);
		}
\end{lstlisting}

\newpage
\section{静态语义分析}
\subsection{实验任务}
本实验要求完成 SysY2022 的语法分析程序。任给一个 SysY2022 语言的源程序，能识别源程序中出现的语义错误。
具体而言，我们需要修改语义检查器 Checker 的源文件 \texttt{src/checker/checker.h} 和 \texttt{src/checker/checker.cpp}，需要能检测出以下语义错误：
\begin{enumerate}
  \item Redefined Variable 当前作用域重复定义变量，以及函数形参重复定义。
  \item Use Undefined Variable 使用未定义变量
  \item Redefined Function 函数重复定义
  \item Use Undefined Function 使用未定义函数
  \item Can not Match Function Parameters 函数参数/类型不匹配，即函数调用必须保证实际参数的个数和类型都与函数声明中的形式参数完全匹配。
  \item Func return type not match 函数返回值类型不匹配, 例如函数返回类型 void/float 时，函数内出现带返回值为 int 的 return 语句
  \item Array index not int 数组下标不是整数
  \item Break not in loop break 语句不在循环中
  \item Continue not in loop continue 语句不在循环中
  \item Visit non-array variable in the form of subscript variables 对非数组变量采用下标变量的形式访问
\end{enumerate}
\subsection{静态语义分析的设计与实现}
通过阅读本任务的代码，我们发现，本任务需要我们实现的是函数返回类型不匹配、函数重复定义、break语句是否在循环体内、continue 语句是否在循环体内、函数未定义、参数长度不匹配、参数类型不匹配这 7 处语义错误的检查和处理。

对于函数返回类型不匹配这一语义错误，我们首先查找函数入口规定的返回值类型，接着和 \texttt{return} 语句后的表达式的类型比较，若不相同，则说明源程序有函数返回类型不匹配的语义错误。
检查和处理错误的代码如下。
\begin{lstlisting}
/**
 *  @brief 访问ReturnStmtAST节点检测语义
 *
 *  @description:
 * 遍历ReturnStmtAST节点，并通过符号表table检测函数返回类型是否与return语句的返回值类型相同。
 *
 *  @param {ReturnStmtAST&} ast - 返回语句的AST节点
 **/
void Checker::visit(ReturnStmtAST &ast) {
  if (ast.exp) {
    ast.exp->accept(*this);
  } else {
    this->current_type.type = TYPE::TYPE_VOID;
  }
  auto entry = find_func();
  // TODO 函数返回类型不匹配
  if (entry->type != this->current_type.type) {
  err.error(ErrorType::FuncReturnTypeNotMatch, "");
  exit(int(ErrorType::FuncReturnTypeNotMatch));
  }
}
\end{lstlisting}

对于函数重复定义这一语义错误，我们在将函数定义插入符号表前遍历符号表查找该函数是否已经存在，若已经存在，则说明源程序有函数重复定义的语义错误。
检查和处理错误的代码如下。
\begin{lstlisting}
  /**
  *  @brief 访问FuncDefAST节点检测语义
  *
  *  @description:
  *将函数插入到符号表中，注意函数不能重复定义，同时进入新函数作用域
  *
  *  @param {FuncDefAST&} ast - 函数定义AST节点
  **/
 void Checker::visit(FuncDefAST &ast) {
   // 将函数插入符号表
   // TODO 函数重复定义
   if (!InsertFunc(ast)) {
   err.error(ErrorType::FuncDuplicated, *ast.id);
   exit(int(ErrorType::FuncDuplicated));
   }
   start_of_new_func = true;
   ast.block->accept(*this);
 }
\end{lstlisting}

对于 \texttt{break / continue} 语句不在循环体内这一语义错误，语义分析程序中维护了一个 \texttt{in\_loop} 变量，表示当前语句是否在循环中。
若正在分析的表达式是 \texttt{break} 或 \texttt{continue} 语句，且 \texttt{in\_loop} 为 \texttt{false}，则说明源程序有 \texttt{break / continue} 语句不在循环体内的语义错误。
检查和处理错误的代码如下。
\begin{lstlisting}
  if (ast.sType == STYPE::BRE) { // 当前节点为Break语句类型
    if (!in_loop) {
      err.error(ErrorType::BreakNotInLoop, "");
      exit(int(ErrorType::BreakNotInLoop));
    }
  } else if (ast.sType == STYPE::CONT) { // 当前节点为Continue语句类型
    if (!in_loop) {
      err.error(ErrorType::ContinueNotInLoop, "");
      exit(int(ErrorType::ContinueNotInLoop));
    }
  }
\end{lstlisting}

对于函数调用过程中的函数未定义、参数长度不匹配、参数类型不匹配这些语义错误，我们在函数调用时进行语义检查。
首先在符号表中查找函数的定义，若未找到，则说明源程序有函数未定义的语义错误。
接着比较符号表中的形参列表长度和当前函数调用传入的实参列表长度是否相同，若不相同，则说明源程序有参数长度不匹配的语义错误。
最后遍历符号表中的形参列表和当前函数调用传入的实参列表并比较对应位置形参和实参的类型，若有至少 1 个形参类型和实参类型不匹配，则说明源程序有参数类型不匹配的语义错误。
检查和处理错误的代码如下。
\begin{lstlisting}
  // 在符号表中查找对应函数
  Entry *entry = Lookup(*ast.id);
  if (entry == nullptr) {
    // TODO ERROR
    // 函数未定义
    err.error(ErrorType::FuncUnknown, *ast.id);
    exit(int(ErrorType::FuncUnknown));
  } else {
    //参数长度不匹配
    if (entry->func_params.size() != ast.funcCParamList.size()) {
      // TODO ERROR
      // 函数参数/类型不匹配
      err.error(ErrorType::FuncParamsNotMatch, *ast.id);
      exit(int(ErrorType::FuncParamsNotMatch));
    } else {
      //遍历实参与形参
      int i = 0;
      for (auto &exp : ast.funcCParamList) {
        exp->accept(*this);
        if (this->current_type.type != entry->func_params[i].type) {
          // TODO ERROR
          // 函数参数/类型不匹配
          err.error(ErrorType::FuncParamsNotMatch, *ast.id);
          exit(int(ErrorType::FuncParamsNotMatch));
        } else {
          i++;
        }
      }
    }
  }
\end{lstlisting}

最后，为了使语义分析程序完整（通过最后 1 个测试点），我们还需要在分析表达式的函数中加入。
\begin{lstlisting}
  if (ast.iterationStmt)
   {
    ast.iterationStmt->accept(*this);
   }
\end{lstlisting}

至此，我们完成了此任务。
\newpage
\section{中间代码生成}
\subsection{实验任务}
本实验要求在 \texttt{genIR.cpp}文件中，实现 \texttt{genIR.h}中说明的 \texttt{visit()} 方法( \texttt{genIR.cpp}的 410 行之后)
\texttt{void visit(StmtAST \&ast) override;} 中，赋值语句的翻译。

\subsection{中间代码生成器的实现}

首先，我们需要解析左值。我们通过设置 \texttt{requireLVal} 为 true，指示在访问左值时需要获取左值的地址。
再调用 \texttt{ast.lVal->accept(*this)} 访问左值，并将结果存储在 \texttt{LVal} 中。
之后我们通过 \texttt{static\_cast<PointerType *>(LVal->type\_)->contained\_} 得到左值指针指向的具体类型。

接着，我们需要访问右值，即调用 \texttt{ast.exp->accept(*this)} 访问右值，并将结果存储在 \texttt{RVal} 中。

然后，我们检查左右值的类型是否匹配，若不匹配则需要做类型转换。如果左值类型为 FLOAT\_T，调用 \texttt{builder->create\_sitofp(recentVal, FLOAT\_T)}将右值转换为浮点类型。
如果左值类型为 INT32\_T，调用 \texttt{builder->create\_fptosi(recentVal, INT32\_T)} 将右值转换为整型。

最后，我们生成 store 指令。调用 \texttt{builder->create\_store(RVal, LVal)}生成 LLVM IR 的 store 指令，存储右值到左值指向的地址。
至此，我们完成了此任务，完整的代码如下。
% \begin{figure}[H]
% 	\begin{center}
% 		\includegraphics[scale=0.25]{images/5-1.png}
% 		\caption{store 中间代码生成}
% 		\label{5-1}
% 	\end{center}
% \end{figure}
\begin{lstlisting}
void GenIR::visit(StmtAST &ast)
{
    switch (ast.sType)
    {
    case SEMI:
        break;
    case ASS:
    {
        // Parse Stmt's LVal
        requireLVal = true;
        ast.lVal->accept(*this);
        auto LVal = recentVal;
        auto LValType = static_cast<PointerType *>(LVal->type_)->contained_;
        // Visit Exp
        ast.exp->accept(*this);
        auto RVal = recentVal;
        // Type swifting
        if (LValType != recentVal->type_)
        {
            if (LValType == FLOAT_T)
            {
                RVal = builder->create_sitofp(recentVal, FLOAT_T);
            }
            else
            {
                RVal = builder->create_fptosi(recentVal, INT32_T);
            }
        }
        builder->create_store(RVal, LVal);
        break;
    }
    case EXP:
        is_single_exp = true;
        ast.exp->accept(*this);
        is_single_exp = false;
        break;
    case CONT:
        builder->create_br(whileCondBB);
        has_br = true;
        break;
    case BRE:
        builder->create_br(whileFalseBB);
        has_br = true;
        break;
    case RET:
        ast.returnStmt->accept(*this);
        break;
    case BLK:
        ast.block->accept(*this);
        break;
    case SEL:
        ast.selectStmt->accept(*this);
        break;
    case ITER:
        ast.iterationStmt->accept(*this);
        break;
    }
}
\end{lstlisting}
\newpage
\section{目标代码生成}
\subsection{实验任务}
本实验要求在 \texttt{codeGen.cc} 中补充代码，实现 \texttt{codeGenerate()} 函数，完成目标代码的生成，能将上一实验生成的 LLVM IR 翻译成 ARMv7 的汇编代码。
\subsection{目标代码生成器的设计与实现}
首先，我们完成初始化部分的代码，我们首先调用一系列初始化函数，注册所有目标、目标信息、目标机器代码、汇编解析器和汇编打印机。
\begin{lstlisting}
  InitializeAllTargetInfos();
  InitializeAllTargets();
  InitializeAllTargetMCs();
  InitializeAllAsmParsers();
  InitializeAllAsmPrinters();
\end{lstlisting}

然后，我们完成设置目标平台部分的代码，设置目标三元组为 riscv64-unknown-elf，即目标平台是 RISC-V 64 位架构的独立可执行格式（ELF）。
\begin{lstlisting}
  auto target_triple = "riscv64-unknown-elf";
  module->setTargetTriple(target_triple);
  std::string error_string;
  auto target = TargetRegistry::lookupTarget(target_triple, error_string);
\end{lstlisting}

最后，我们完成初始化 \texttt{addPassesToEmitFile()}的参数的代码。我们按照以下顺序进行初始化。
\begin{enumerate}
  \item 调用 \texttt{getGenFilename} 函数获取要生成的目标文件的文件名。
  \item 创建 \texttt{raw\_fd\_ostream}对象 \texttt{dest}，用于输出目标文件。如果创建失败，打印错误信息并返回1。
  \item 创建 \texttt{legacy::PassManager} 对象 \texttt{pass}，用于管理优化和代码生成的各个通道。
  \item 设置文件类型为 \texttt{gen\_filetype}。
\end{enumerate}
\begin{lstlisting}
    auto filename = getGenFilename(ir_filename, gen_filetype);
    std::error_code EC;
    raw_fd_ostream dest(filename, EC, sys::fs::OF_None);
    if (EC)
    {
      printf("Error occured!\n");
      return 1;
    }
    legacy::PassManager pass;
    auto file_type = gen_filetype;
\end{lstlisting}

至此，我们完成了此任务。

\newpage
\section{总结}
\subsection{实验感想}
通过本次编译原理实验，我深刻体会到了编译器设计的复杂性与精妙之处。
起初，我认为编译工具链的使用只是单纯地调用几个命令行工具，
但随着实验的深入，我逐渐意识到每一个环节背后都有复杂的算法和数据结构的支持。
特别是在词法分析和语法分析阶段，通过手动编写 flex 和 bison 支持的词法规则和语法规则，我对正则表达式和上下文无关文法有了更加深入的理解。
同时，在静态语义分析阶段，构建语义检查程序让我明白了编译器如何在编译期间确保程序的语义正确性。
在中间代码生成和目标代码生成的过程中，我看到了一段高级语言代码如何逐步转化为机器能够执行的低级代码，
这不仅提高了我的编程能力，也让我对编译原理的理论有了更深入的认识。

\subsection{实验总结与展望}
通过本次实验，我掌握了编译器前端和后端的基本原理和实现方法。
具体来说，我学会了如何使用 flex 和 bison 进行词法和语法分析，如何通过语法树进行语义分析，
以及如何生成中间代码和目标代码。整个实验过程让我认识到，编译器不仅是将高级语言转化为机器语言的工具，
更是一个复杂的系统工程，每个环节都需要严谨的设计和实现。

另外，以下是对实验的三点建议：
\begin{enumerate}
  \item 实验的未公开测试点可以设置访问权限，不然可以通过读取文件的方式获取未公开的测试点的内容。
  \item 实验的测试程序可以编译成目标代码或 lib 库再提供，不然可以直接面向测试程序编程或者直接改测试程序。
  \item 建议提供实验报告的 \LaTeX 模板，减少同学们在调格式时花费的时间。
\end{enumerate}

% \begin{figure}[htb] % here top bottom
% 	\begin{center}
% 		\includegraphics[scale=0.80]{images/1-1.pdf}
% 		\caption{网页整体框架举例}
% 		\label{fig5-1}
% 	\end{center}
% \end{figure}



% \nocite{*} %% 作用是不对文献进行引用，但可以生成文献列表

% \bibliographystyle{Experimental_Report}
% \bibliography{Experimental_Report}
% \setcounter{secnumdepth}{0}
% \appendix

\end{document}